import java.util.Stack;

public class QuickSort {
    public static void quickSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }

//         // 优化3.1 三数取中法
//        int index = threeMid(array,left,right);
//        swap(array,index, left);

//        //优化3.2 递归到小的子区间时，可以考虑使用插入排序
//        if(right-left+1<=100){
//            insertSort(array,left,right);
//        }

        int div=partition(array, left, right);//隔断

        quickSort(array, left, div-1);
        quickSort(array, div+1, right);
    }

    //挖坑法          找基准
    private static int partition(int[] array, int left, int right) {
        int pivot=array[left];
        int i=left;
        int j=right;
        while(i<j){
            while (i < j && array[j] >= pivot) {
                j--;
            }
            array[i]=array[j];
            while (i < j && array[i] <= pivot) {
                i++;
            }
            array[j]=array[i];
        }
        array[i]=pivot;
        return i;
//        int pivot=array[left];
//        while(left<right){
//            while (left < right && array[right] >= pivot) {
//                right--;
//            }
//            array[left]=array[right];
//            while (left < right && array[left] <= pivot) {
//                left++;
//            }
//            array[right]=array[left];
//        }
//        array[left]=pivot;
//        return left;
    }

    //士兵法
    public static void quickSort1(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int div=partition1(array, left, right);//隔断

        quickSort(array, left, div);
        quickSort(array, div+1, right);
    }
    private static int partition1(int[] array, int left, int right) {
        int pivot=array[left];
        int i=left;
        int j=right;
        while(i<j){
            //i一定要在j前面？，为什么？
            while (i<j&&array[j]>=pivot){
                j--;
            }
            while (i<j&&array[i]<=pivot){
                i++;
            }

            swap(array,i,j);
        }
        swap(array,left,i);
        return i;
    }



    public static void main(String[] args) {
        int[] array1={0,5,9,7,8,3,1,2,6,4,0};
        //quickSort(array1,0,10);
        quickSort2(array1);
        for (int x:
                array1) {
            System.out.println(x);
        }
        System.out.println("-------");
    }



    //返回三数下标
    private static int threeMid(int[] array,int left,int right) {
        int mid = (left+right) >>> 1;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            // array[left] > array[right]
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }

    private static void swap(int[] array,int i,int j){
        int tmp= array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void insertSort(int[] array,int left,int right){
        for(int i=left+1;i< right;i++){

            //挖坑--保存数据
            int insertVal=array[i];
            int insertFront=i-1;

            // 找到应该插入的位置&位置数据右移
            for (;insertFront>=0;insertFront--) {
                if (array[insertFront] > insertVal) {
                    array[insertFront + 1] = array[insertFront];
                } else
                    break;
            }
            //因为之前--后退出，所以加回去
            array[insertFront+1]=insertVal;
        }
    }
    public static void quickSort2(int[] array) {
        Stack<Integer> stack = new Stack<>();

        int start = 0;
        int end = array.length-1;
        int pivot = partition(array,start,end);

        //左边有2个元素及以上
        if(pivot > start+1) {
            stack.push(start);
            stack.push(pivot-1);
        }
        //右边有2个元素及以上
        if(pivot < end-1) {
            stack.push(pivot+1);
            stack.push(end);
        }

        while (!stack.empty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array,start,end);

            //左边有2个元素及以上
            if(pivot > start+1) {
                stack.push(start);
                stack.push(pivot-1);
            }
            //右边有2个元素及以上
            if(pivot < end-1) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }
}

